1. Field of Invention
This invention relates to methods and systems that model and reconstruct continuous tone or grayscale images from halftoned binary images. More specifically, this invention is directed to methods and systems that convert or reconvert through modeling and reconstruction halftoned binary images into approximations of the original continuous tone images using template matching.
2. Description of Related Art
Conventionally, a typical black and white image on photographic film, for example, includes various gray levels of light. That is, different amounts of light are reflected from various spots of the image on the film, providing what is known as a continuous tone photographic image. It is conventionally known how to digitize the grayscale continuous tone photographic image. More specifically, each pixel or spot of the photographic image is assigned a number representing the amount of light or gray level of that particular spot. Typically, an eight-bit word is used, giving 256 different digitized gray levels of light. The digitized image is known as a continuous tone digital image. Further, it is possible to go back and forth between the analog and digital images and maintain a reasonable reproduction of the image.
It is also conventionally known to provide an image on a recording medium, for example, a paper sheet, rather than on photographic film. For example, a modulated laser can be used to scan a xerographic drum to give a series of black and white spots. The spots are formed by turning the laser on and off. The image on the drum is then developed and transferred to a copy sheet. This process of developing black and white spots provides a binary image, but does not generate a continuous tone image.
It is possible, however, to give the impression of a continuous tone image by using halftoning. The halftone process uses a mathematically stored screen pattern, for example, which is an almost-sinusoidal two-dimensional pattern. The process converts the original or continuous tone image into an image of black and white spots that xe2x80x9cappearsxe2x80x9d to be a continuous tone image. This process is generally accomplished by systematically comparing each pixel""s continuous tone value with the value of the screen. If the continuous tone value of the pixel is less dense than the screen value, then a white spot is produced. On the other hand, if the pixel value is more dense than the screen value, a black spot is produced. It should be understood that the pixel values are the 8-bit grayscale values for each pixel of the original image.
In effect, this procedure converts a grayscale image into black and white spots, but gives the impression of multiple gray levels by producing more white spots for a less-dense area and more black spots for a denser area. Although a true continuous tone image is not produced by this procedure, the procedure has two advantages. One advantage is that each spot of the image is described with one bit, rather than the eight-bit word used for each gray level pixel in the original continuous tone picture. This allows the halftone image to be stored with approximately xe2x85x9 of the storage of the original continuous tone image. Another advantage is that, in fact, a halftone image can be printed on paper. In other words, the conversion takes each eight-bit pixel value representing a grayscale value, compares the pixel value to a screen value and provides either a zero (0) or a one (1) to modulate the laser. This image can then be printed on a recording medium such as paper.
Another known halftoning method is called error-diffusion. Typical applications of error diffusion include viewing continuous tone images on low resolution displays and generating bitmaps for binary printers. Error diffusion is an adaptive binarization process which has the property of preserving the local average gray level of the input continuous tone image. Specifically, error-diffusion propagates the error generated during binarization to neighboring pixels.
Accordingly, if all that is required is printing of the stored halftone image, then there is no difficulty. However, if it becomes necessary to modify the image, for example, to magnify or to change the tone scale, the continuous tone image is often not available. It is then necessary to go back to the original continuous tone image, with the eight-bit words representing the grayscale value of each pixel, to make the modification. However, because this original image requires eight times the storage capacity of the stored halftone image, it is often no longer available. If the original image is no longer available, then the halftone image needs to be converted back to an estimated grayscale image, which represents the original continuous tone image. Clearly, reversing the halftoning process should be performed as accurately and efficiently as possible.
The process of digital inverse halftoning is the process of reconverting a binary image into an approximation of the original grayscale image. Inverse halftoning can be applied to a wide variety of binary image processing applications. Illustratively, inverse halftoning may be used in conjunction with scaling, tone correction, interchanging between halftone methods, facsimile image processing, non-linear filtering, enhancement and/or image compression, for example.
Image conversion between a binary image and a grayscale image is often necessary. Illustratively, image conversion may be necessary where multiple devices are connected together and must communicate with each other. For example, devices such as a scanner, a personal computer or a facsimile machine may be connected such that they are in communication with each other. Often a network is utilized to connect these various devices. In a networked environment, images may be preprocessed for a particular printer. However, it may be necessary to transmit or communicate these images to a second, different, printer. The second printer may have a different printing strategy than the first printer. For example, the second printer could have a different resolution, a different tonal response, and/or a different halftoning method than the first printer. Under such conditions, it may be necessary or desirable to recover the grayscale image information and perform device specific corrections before printing.
It should be appreciated that it is impossible to exactly reverse the halftoning process to recreate the original continuous tone image, since some information has been lost during halftoning and is simply not recoverable. However, just as the halftone image gives the visual impression of grayscale values, conventional methods may be used to reconstruct an approximation of the original continuous tone image.
A partial solution known in the art approximates the original continuous tone image by spatially filtering the halftone image with a low pass filter. This process uses an averaging procedure on the halftone image and yields a reconstructed continuous tone image. The reconstructed image, however, provides a blurred image without sharp lines.
Further, there are a number of other conventional methods and approaches to inverse halftoning. Some of these conventional methods relate to dithered images. When using dithered images, one technique utilizes a neighborhood approach. The neighborhood approach uses adaptive run lengths of 1""s and 0""s, referred to as the adaptive binary run length (ABRL). This method performs particularly well in a three-step cascade algorithm comprised of ABRL, statistical smoothing and impulse removal.
Thus, the conventional methods and techniques described above have various shortcomings associated with them. Specifically, the conventional methods and techniques described above do not provide optimized methods to perform inverse halftoning to convert halftoned binary images into approximations of the original continuous tone image.
Accordingly, this invention provides improved systems and methods that model and reconstruct grayscale images from halftoned images.
This invention separately provides systems and methods that match templates to pixel patterns in the halftone images.
This invention separately provides systems and methods that reconstruct a grayscale image from a binary image by matching patterns of pixels that occur in the binary image to corresponding grayscale values.
This invention separately provides systems and methods that develop a correspondence between grayscale values and patterns of pixels in a binary image based on a baseline image and a binary image generated from the baseline image.
This invention separately provides systems and methods that develop a correspondence between grayscale values and classes of patterns of pixels in a binary image, where the classes are formed by rotations of the pixel patterns.
This invention separately provides systems and methods that model and reconstruct grayscale images from halftone images while still maintaining a relatively sharp image by not blurring the grayscale image.
According to one exemplary embodiment of the systems and methods according to this invention, a look-up table is optimally generated using a set of one or more training images. A given bit pattern will have a specific number of occurrences in a training sequence. For all the occurrences of a given bit pattern in a training sequence, the corresponding gray levels in the training sequence are recorded. The mean value of the graylevels for a corresponding bit pattern is computed. The mean value, thus computed, will be the gray level corresponding to the given bit pattern. Thus, in this exemplary embodiment of the systems and methods of this invention, the inverse halftoning systems and methods essentially perform a decoding operation. More specifically, the decoder of the decoding operation is implemented using the look-up table. The look-up table associates a particular grayscale value with a particular bit pattern.
Illustratively, as described in the various embodiments of the invention discussed herein, the methods and systems of the invention may be applied to error-diffused images. However, it should be recognized that the systems and methods of the invention are not limited to error-diffused images. Rather, the systems and methods of the invention may be used in conjunction with a variety of halftoning processes. For example, the systems and methods of the invention may also be used in conjunction with images that have been converted using an ordered dither method, for example.
In accordance with one exemplary embodiment of the systems and methods of this invention, a training process is initially performed. The training process involves a template matching process. The template matching process is trained based on a test pattern image. The correspondence between certain templates of pixels in a binary image formed from the test pattern image and the grayscale values of the test pattern image for the certain templates is generated by converting the grayscale test pattern to a halftone image. The pixel patterns resulting from each grayscale level of the test pattern are recorded. The recorded grayscale values are then used in place of a target pixel of the corresponding pixel patterns when generating a reconstructed grayscale image from the halftoned image.
Illustratively, a continuous tone grayscale image may be converted to a binary image for various reasons including, for example, electronic storage limitations. The binary image may be in the form of an error-diffused halftone image. In accordance with the systems and methods of this invention, it has been recognized that portions of the binary image form patterns of pixels. These patterns may be characterized by a unique set of templates. Certain pixel patterns are 90 degree rotations of each other. The method and systems of the invention use this relationship between certain pixels to increase the efficiency of the inverse halftoning process. The unique set of templates allows efficient construction of a look-up table. The look-up table provides an association between a set of one or more specific pixel patterns in a binary image and a grayscale value associated with the one or more patterns.
In accordance with the systems and methods of this invention, the look-up table is provided. According to systems and methods of this invention, an observation window is used to select pixels as input patterns to the look-up table. Illustratively, a 3xc3x973 observation window may be used. The look-up table can have a reduced number of entries due to the fact that some patterns that characterize a particular gray level are rotations of each other. For example, the number of entries in the look-up table may be reduced to 132 entries. The look-up table thus obtained is used for reconstructing an accurate 8-bit recreation of the original grayscale image. As a result of the systems and methods according to this invention, the peak signal to noise ratio (PSNR) is greatly increased compared to the conventional methods. The systems and methods of this invention may also be applied to error-diffused color images by generating and using a look-up table for each of the color separation layers.
These and other features and advantages of the systems and methods of this invention are described in or are apparent from the following detailed description of the exemplary embodiments.